function swap(nums, i, j) {
  const temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

function bubbleSort(nums) {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = 0; j < nums.length - 1 - i; j++) {
      if (nums[j] > nums[j + 1]) swap(nums, j, j + 1);
    }
  }
  return nums;
}

function selectSort(nums) {
  for (let i = 0; i < nums.length - 1; i++) {
    let minIndex = i;
    for (let j = i; j < nums.length; j++) {
      if (nums[j] < nums[minIndex]) minIndex = j;
    }
    swap(nums, i, minIndex);
  }
  return nums;
}

function insertSort(nums) {
  for (let i = 1; i < nums.length; i++) {
    for (let j = i; nums[j] < nums[j - 1] && j > 0; j--) {
      swap(nums, j, j - 1);
    }
  }
  return nums;
}

function shellSort(nums) {
  for (
    let gap = Math.floor(nums.length / 2);
    gap > 0;
    gap = Math.floor(gap / 2)
  ) {
    for (let i = gap; i < nums.length; i++) {
      for (j = i; j - gap >= 0 && nums[j] < nums[j - gap]; j -= gap)
        swap(nums, j, j - gap);
    }
  }
  return nums;
}

function quickSort(nums) {
  subSort(nums, 0, nums.length - 1);
  return nums;
}

function subSort(nums, start, end) {
  if (start > end) return;
  let i = start,
    j = end;
  while (i < j) {
    while (i < j && nums[i] <= nums[j]) i++;
    swap(nums, i, j);
    while (i < j && nums[i] < nums[j]) j--;
    swap(nums, i, j);
  }
  subSort(nums, start, i - 1);
  subSort(nums, i + 1, end);
}

function mergeSort(nums) {
  if (nums.length <= 1) return nums;
  const mid = Math.floor(nums.length / 2);
  const nums1 = mergeSort(nums.slice(0, mid));
  const nums2 = mergeSort(nums.slice(mid));
  return merge(nums1, nums2);
}

function merge(nums1, nums2) {
  const result = [];
  let i = 0;
  j = 0;
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] < nums2[j]) result.push(nums1[i++]);
    else result.push(nums2[j++]);
  }
  while (i < nums1.length) result.push(nums1[i++]);
  while (j < nums2.length) result.push(nums2[j++]);
  return result;
}

function countingSort(nums) {
  const max = Math.max(...nums);
  const buckets = new Array(max + 1).fill(0);
  const result = [];
  nums.forEach((item) => {
    buckets[item]++;
  });
  buckets.forEach((item, index) => {
    while (item--) result.push(index);
  });
  return result;
}

function bucketSort(nums) {
  const max = Math.max(...nums);
  const min = Math.min(...nums);
  const bucketNum = Math.floor((max - min) / 5) + 1;
  const buckets = new Array(bucketNum).fill(0).map(() => []);
  nums.forEach((item) => {
    const index = Math.floor((max - min) / 5);
    buckets[index].push(item);
  });
  buckets.forEach((bucket) => bucket.sort());
  const result = [];
  buckets.forEach((bucket) => {
    result.push(...bucket);
  });
  return result;
}

function radixSort(nums) {
  const max = Math.max(...nums);
  let base = 1;
  const temp = nums.slice();
  const buckets = new Array(10).fill(0).map(() => []);
  while (base <= max) {
    temp.forEach((item) => {
      const index = Math.floor(item / base) % 10;
      buckets[index].push(item);
    });
    temp.length = 0;
    buckets.forEach((bucket) => {
      temp.push(...bucket);
      bucket.length = 0;
    });
    base *= 10;
  }
  return temp;
}

console.log("bubbleSort", bubbleSort([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log("selectSort", selectSort([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log("insertSort", insertSort([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log(
  "quickSort",
  quickSort([1, 4, 2, 7, 5, 1, -1000, 49935, -4, 777, 0, 9, 1, 4, -30, 0, 9, 4])
);
console.log("mergeSort", mergeSort([1, 4, 2, 7, 5, 1, 0, 9, 4]));
console.log(
  "countingSort",
  countingSort([
    1, 4, 2, 7, 5, 1, -1000, 49935, -4, 777, 0, 9, 1, 4, -30, 0, 9, 4,
  ])
);
console.log(
  "bucketSort",
  bucketSort([
    1, 4, 2, 7, 5, 1, -1000, 49935, -4, 777, 0, 9, 1, 4, -30, 0, 9, 4,
  ])
);
console.log(
  "shellSort",
  shellSort([1, 4, 2, 7, 5, 1, -1000, 49935, -4, 777, 0, 9, 1, 4, -30, 0, 9, 4])
);
console.log("radixSort", radixSort([10, 44, 22, 72, 5989, 100, 30, 99, 498]));
